package jdk8Demo;

public class ErFenSearch {
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		int needFindData = 3;
		int[] beforeArray = { 3, -1, 0, 1, 5, 6, 1, 3 };
		display(beforeArray);

		int array[] = quickSort(beforeArray, 0, beforeArray.length - 1);
		display(array);
		int left = 0;
		int right = array.length - 1;
		int findIndex = searchData(array, needFindData, left, right);
		if (-1 != findIndex) {
			System.out.println("你所找的数据在第" + (findIndex + 1) + "位");
		} else {
			System.out.println("你所找的数据不存在");
		}
		long endTime = System.currentTimeMillis();
		long handleTime = endTime - startTime;
		System.out.println("共花费时间：" + handleTime + "ms");
	}

	public static int searchData(int[] array, int needFindData, int left, int right) {
		// TODO Auto-generated method stub
		if (null != array && array.length > 0) {
			int index = (left + right) / 2;
			if (needFindData < array[left] || needFindData > array[right]) {
				return -1;
			} else if (array[index] == needFindData) {
				return index;
			} else if (array[index] < needFindData) {
				return searchData(array, needFindData, index + 1, right);
			} else if (array[index] > needFindData) {
				return searchData(array, needFindData, left, index - 1);
			}
		}
		return -1;
	}

	public static int[] quickSort(int[] array, int left, int right) {
		if (null != array && array.length > 0 && left <= right) {
			int position = findQieIndex(array, left, right);
			quickSort(array, left, position - 1);
			quickSort(array, position + 1, right);
		}
		return array;
	}

	public static int findQieIndex(int[] array, int left, int right) {
		// TODO Auto-generated method stub
		int key = array[left];
		while (left < right) {
			while (left < right && array[right] >= key) {
				right--;
			}
			swap(array, left, right);
			while (left < right && array[left] <= key) {
				left++;
			}
			swap(array, left, right);
		}
		return left;
	}

	public static void swap(int[] array, int left, int right) {
		// TODO Auto-generated method stub
		int temp;
		if (array != null && array.length > 0) {
			temp = array[left];
			array[left] = array[right];
			array[right] = temp;
		}
	}

	public static void display(int[] array) {
		for (int a : array) {
			System.out.print(a + ",");
		}
		System.out.println("");
	}
}
